22. 受限序列重排

题目内容

给定一个包含 n 个整数的数组 A 和一个整数 k，你需要将数组 A 中的所有元素重新排列，生成一个新的序列数组，其中下标第 k-1 个元素和下标第 k 个元素不能数值相同。请输出重新排列后符合条件的数组个数（相同数组排列需去重统计）；如果无法构造出满足上述所有条件的数组，输出 0。

输入描述

• n：数组长度，1 ≤ n ≤ 15
• k：限制索引，1 ≤ k ≤ n-1
• A：数组元素 A0...An-1，其中 1 ≤ Ai ≤ 100

输出描述

输出符合排列组合条件的数组个数。

样例

样例 1

输入

3
1
2 2 3

输出

2

说明： 只存在 3 2 2 和 2,3,2 两种合法情况。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let lines = [];
rl.on('line', (input) => {
    lines.push(input.trim());
});

rl.on('close', () => {
    const n = parseInt(lines[0]);
    const k = parseInt(lines[1]);
    const A = lines[2].split(/\s+/).map(Number);

    // 排序，方便去重
    A.sort((a, b) => a - b);

    const used = new Array(n).fill(false);
    const result = [];  // 当前排列
    let count = 0;

    function dfs(pos) {
        // 所有位置都填完了
        if (pos === n) {
            count++;
            return;
        }

        for (let i = 0; i < n; i++) {
            if (used[i]) continue;

            // 去重：相同元素，前一个没用过，则跳过
            if (i > 0 && A[i] === A[i - 1] && !used[i - 1]) continue;

            // 限制：如果当前填的是第 k 个位置，检查与前一个是否相同
            if (pos === k && result[pos - 1] === A[i]) continue;

            used[i] = true;
            result.push(A[i]);
            dfs(pos + 1);
            result.pop();
            used[i] = false;
        }
    }

    dfs(0);
    console.log(count);
});